home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_13_12 / colvin / gc.cpp < prev    next >
C/C++ Source or Header  |  1995-10-10  |  7KB  |  243 lines
  1. ////////////////////////////////////////////////////////////
  2. // gc.cpp                     Copyright 1995 Gregory Colvin.
  3. //                    Free distribution OK with this notice.
  4. //
  5. // MSDOS implementation of mark-sweep garbage collection.
  6. // Assumes that arrays with destructors have a four byte
  7. // element count immediately preceding array data.
  8. // Assumes that vptr is at the beginning of an object.
  9. // Tested with Borland C++ 4, 16-bit large memory model.
  10. #include <dos.h>
  11. #include "runtime.h"
  12. #include "gc.h"
  13.  
  14. // DOS memory segments are aligned on 16 byte paragraph
  15. // boundaries, addressable with two bytes (16 Meg limit).
  16. const size_t MIN_SEG=16;
  17. typedef unsigned short SEG, OFF;
  18. typedef void* PTR;
  19.  
  20. // State of the memory allocator.
  21. static new_handler ChainedHandler;
  22. static SEG Heap, Rover, End;
  23. static unsigned NAlloc;
  24.  
  25. // Access to memory segment header and data. At the head
  26. // of each allocated segment we keep three tag bits, the 
  27. // number of paragraphs allocated, and a count of the number
  28. // of roots pointing into it. A root is any gc_link which
  29. // is not on the heap, or is on the heap but locked.
  30. struct gc_hdr {
  31.    unsigned mark :  1;  // mark as reachable
  32.    unsigned lock :  1;  // lock against collection
  33.    unsigned mult :  1;  // true for arrays
  34.    unsigned null :  1;  // unused, must be 0
  35.    unsigned size : 12;  // number of allocated paragraphs
  36.    unsigned root : 16;  // number of roots pointing in
  37.  
  38.    void Clear(unsigned n) { memset(this,0,n*MIN_SEG); }
  39.    void Clear()           { Clear(size); }
  40. };
  41.  
  42. inline SEG Seg(PTR p)       { return FP_SEG(p); }
  43. inline OFF Off(PTR p)       { return FP_OFF(p); }
  44. inline PTR Ptr(SEG s,OFF o) { return MK_FP(s,o); }
  45.  
  46. inline gc_hdr&  Hdr (SEG s) { return *(gc_hdr*) Ptr(s,0); }
  47. inline gc_data& Data(SEG s) { return *(gc_data*)Ptr(s,4); }
  48.  
  49. inline bool OnHeap(SEG s) { return Heap <= s && s <= End; }
  50. inline bool IsRoot(SEG s) { return !OnHeap(s)||Hdr(s).lock;}
  51.  
  52. inline unsigned NSeg(size_t n_bytes) {
  53.    return (sizeof(gc_hdr) + n_bytes + MIN_SEG - 1)/MIN_SEG;
  54. }
  55.  
  56. // Initialize statics and clean up when done.
  57. struct gc_statics {
  58.    gc_statics() {          // take all but 4K of heap for GC
  59.       unsigned heap_size;
  60.       _dos_allocmem(0xFFFF,&heap_size);
  61.       PTR p = halloc(heap_size -= 0xFF,MIN_SEG);
  62.       if (!p)
  63.          abort();
  64.       Heap = Seg(p) + 1;
  65.       Rover = End = Heap + heap_size - 2;
  66.       Hdr(End).Clear(1); Hdr(End).lock = Hdr(End).size = 1;
  67.       do Hdr(--Rover).Clear(1); while (Rover > Heap);
  68.       ChainedHandler= set_new_handler(gc_min);
  69.    }
  70.    ~gc_statics() { gc_all(); }
  71. };
  72.  
  73. // Full collection.
  74. void gc_all() {
  75.    do gc_data::Mark(); while (gc_data::Sweep());
  76. }
  77.  
  78. // Partial collection.
  79. void gc_min() {
  80.    gc_data::Mark(); 
  81.    gc_data::Sweep();
  82. }
  83.  
  84. // Partial collection suitable for use as new-handler.
  85. void gc_handler() throw(bad_alloc) {
  86.    gc_data::Mark(); 
  87.    if (!gc_data::Sweep()) {
  88.       if (ChainedHandler)
  89.          ChainedHandler();
  90.       throw bad_alloc();
  91.    }
  92. }
  93.  
  94. // Allocate segments. 
  95. void* allocate(size_t size) throw() {
  96.    static gc_statics init;
  97.    unsigned n= NSeg(size);
  98.  
  99.    // loop over heap looking for enough free space
  100.    for (SEG r,s=Rover,end=End; ; end=Rover,s=Heap) {
  101.       do {
  102.          r = s;
  103.          while (Hdr(s).size == 0)
  104.             if (++s - r >= n) {
  105.                Rover = r + n;
  106.                NAlloc += n;
  107.                Hdr(r).lock = 1;              // locked
  108.                Hdr(r).size = n;
  109.                return Ptr(r,sizeof(gc_hdr)); // success
  110.             }
  111.          assert(Hdr(s).null==0);
  112.       } while ((s += Hdr(s).size) < end);
  113.       if (s == Rover)
  114.          return 0;                           // failure
  115.    }
  116. }
  117.  
  118. // Deallocate segments by zero filling.
  119. void deallocate(void* p) throw() {
  120.    if (p) {
  121.       SEG s= Seg(p);
  122.       gc_hdr& hdr= Hdr(s);
  123.       assert(!hdr.root);
  124.       NAlloc -= hdr.size;
  125.       hdr.Clear();
  126.    }
  127. }
  128.  
  129. // Mark garbage collected data temporarily on construction.
  130. gc_data::gc_data() {
  131.    Hdr(Seg(this)).mark = 1;
  132. }
  133.  
  134. // Walk the heap and cause the gc_value assignment
  135. // operator to recursively mark roots.
  136. int gc_data::IsMarking;
  137. struct gc_marking {
  138.    gc_marking() { gc_data::IsMarking = 1; }
  139.    ~gc_marking() { gc_data::IsMarking = 0; }
  140. };
  141. void gc_data::Mark() {
  142.    if (IsMarking) 
  143.       throw bad_alloc();
  144.    struct gc_marking marker;
  145.    for (SEG s=Heap; s < End; ) {
  146.       assert(Hdr(s).null==0);
  147.       gc_hdr& hdr= Hdr(s);
  148.       unsigned n= hdr.size;
  149.       if (n) {
  150.          if (hdr.root && !hdr.mark)
  151.             Data(s).mark_all();
  152.          s += n;
  153.       } else
  154.          s++;
  155.    }
  156. }
  157.  
  158. // Sweep heap to collect garbage. If data is marked then
  159. // clear the mark for the next sweep, else destroy data.
  160. int gc_data::Sweep() {
  161.    int released=0;
  162.    for (SEG s=Heap; s < End; ) {
  163.       assert(Hdr(s).null==0);
  164.       gc_hdr& hdr= Hdr(s);
  165.       unsigned n= hdr.size;
  166.       if (n) {
  167.          if (!hdr.lock)
  168.             if (hdr.mark)
  169.                hdr.mark = 0;
  170.             else {
  171.                Data(s).destroy_all();
  172.                released = 1;
  173.             }
  174.          s += n;
  175.       } else
  176.          s++;
  177.    }
  178.    return released;
  179. }
  180.  
  181. // Loop over data to mark or destroy each contained value.
  182. void gc_data::mark_loop(size_t size) {
  183.    char* p= (char*)&this->data;
  184.    gc_hdr& hdr= Hdr(Seg(this));
  185.    if (hdr.mult) {                  // if multiple elements
  186.       unsigned n= *(unsigned long*)p;
  187.       for (p += 4; n--; p += size)  // loop over n elements
  188.          mark(p);
  189.    } else
  190.       mark(p);                      // only one element
  191.    hdr.mark = 1;
  192. }
  193. void gc_data::destroy_loop(size_t size) {
  194.    char* p= (char*)&this->data;
  195.    gc_hdr& hdr= Hdr(Seg(this));
  196.    if (hdr.mult) {                  // if multiple elements
  197.       unsigned n= *(unsigned long*)p;
  198.       for (p += 4; n--; p += size)  // loop over n elements
  199.          destroy(p);
  200.    } else
  201.       destroy(p);                   // only one element
  202.    deallocate(this);
  203. }
  204.  
  205. // Assignment of gc_links is magic in Marking mode.
  206. void gc_link::mark_or_copy(const gc_link& r) {
  207.    if (gc_data::IsMarking) {
  208.       SEG s= Seg(ptr);
  209.       if (s && Hdr(s).size)
  210.          Data(s).mark_all();
  211.    } else
  212.       set_ptr(r.ptr);
  213. }
  214.  
  215. // Maintain root counts for gc_links. 
  216. void gc_link::incr_root() {
  217.    SEG s= Seg(ptr);
  218.    if (OnHeap(s) && IsRoot(Seg(this)))
  219.       ++Hdr(s).root;
  220. }
  221. void gc_link::decr_root() {
  222.    SEG s= Seg(ptr);
  223.    if (OnHeap(s) && IsRoot(Seg(this)))
  224.       --Hdr(s).root;
  225. }
  226. void gc_link::set_ptr(void* p) {
  227.    decr_root();
  228.    if (ptr = p) {
  229.       SEG s= Seg(p);
  230.       if (OnHeap(s)) {                 // if allocated
  231.          gc_hdr& hdr= Hdr(s);
  232.          if (hdr.mark) {               // if to be collected
  233.             hdr.mark = hdr.lock = 0;   // safe to unlock
  234.             hdr.mult                   // detect arrays
  235.                = Off(p) > gc_data::min() + sizeof(gc_hdr);
  236.          }
  237.       }
  238.       incr_root();
  239.    }
  240. }
  241.  
  242.  
  243.